/**
 * @a https://leetcode.cn/problems/multiply-strings/
 */


#include "common.h"



class Solution {
public:
    string multiply(string num1, string num2) {
        if(num1 == "0" || num2 == "0") return "0";
        int n1 = num1.size();
        int n2 = num2.size();
        reverse(num1.begin(), num1.end());
        reverse(num2.begin(), num2.end());
    
        vector<int> tmp(n1 + n2 - 1);
        for(int i = 0; i < n1; ++i)
            for(int j = 0; j < n2; ++j)
                tmp[i + j] += (num1[i] - '0') * (num2[j] - '0');

        int sum = 0;
        string ret;
        for(int i = 0; i < n1 + n2 - 1 || sum; ++i){
            if(i < n1 + n2 - 1) sum += tmp[i];
            ret += (sum % 10) + '0';
            sum /= 10;
        }
        while(ret.size() > 1 && ret.back() == '0') ret.pop_back();
        reverse(ret.begin(),ret.end());
        return ret;
    }
};



class Solution {
public:
    string multiply(string num1, string num2) {
        if(num1 == "0" || num2 == "0") return "0";
        int n1 = num1.size();
        int n2 = num2.size();
        reverse(num1.begin(), num1.end());
        reverse(num2.begin(), num2.end());

        vector<int> tmp(n1 + n2 - 1);
        for(int i = 0; i < n1; ++i)
            for(int j = 0; j < n2; ++j)
                tmp[i+j] += (num1[i] - '0') * (num2[j] - '0');

        int sum = 0;
        string ret;
        for(int cur = 0; cur < n1 + n2 - 1 || sum; ++cur){
            if(cur < n1 + n2 - 1){
                sum += tmp[cur];
            }
            ret += (sum % 10) + '0';
            sum /= 10;
        }
        // 前导零
        while(ret.size() > 1 && ret.back() == '0') ret.pop_back();
        reverse(ret.begin(), ret.end());
        return ret;
    }
};